package jianzhiOffer;

import java.util.ArrayList;
import java.util.List;

public class Num053 {
    List<TreeNode> res = new ArrayList<>();
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root);
        int index = 0;
        for(TreeNode n : res) {
            if(n.val == p.val) {
                break;
            }
            index++;
        }
        return index == res.size() - 1 ? null : res.get(index + 1);
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.left);
        res.add(root);
        dfs(root.right);
    }
}
